#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <sys/time.h>
#include <string.h>
#include "graph.h"
#include "euler.h"
#include "common.h"


void broadcastGraph(Graph* graph, int rank, int numProc) {
	int		i, j, conns, proc;
	int		startNode, endNode;
	Node*	node;
	
	MPI_Bcast(&graph->numNodes, 1, MPI_INT, 0, MPI_COMM_WORLD);
	
	/* will exit when the params were invalid or when 0 nodes are declared in the input file */
	if (0 == graph->numNodes) {
		MPI_Finalize();
		exit(0);
	}
	
	if (0 != rank) {
		graph->nodes = new(Node, graph->numNodes);
		graph->dists = new(double, graph->numNodes);
		graph->prev = new(int, graph->numNodes);
	}

	/* We won't bother with sending only select vertices to other nodes. Too much hassle in this simple program */
	MPI_Bcast(graph->dists, graph->numNodes, MPI_DOUBLE, 0, MPI_COMM_WORLD);
	MPI_Bcast(graph->prev, graph->numNodes, MPI_INT, 0, MPI_COMM_WORLD);
	

	for (i = 0; i < graph->numNodes; ++i) {
		node = &graph->nodes[i];

		/* Send the node's connections and connection distances to processes */
		if (0 == rank) {
			for (proc = 1; proc < numProc; ++proc) {
				
				/* Only send connections >= startNode and < endNode */
				startNode	= (proc+0) * graph->numNodes / numProc;
				endNode	= (proc+1) * graph->numNodes / numProc;
				
				conns = 0;
				for (j = 0; j < node->numConns; ++j) {
					if (node->conns[j] >= startNode && node->conns[j] < endNode) {
						++conns;
					}
				}
				
				MPI_Send(&conns, 1, MPI_INT, proc, 0, MPI_COMM_WORLD);

				for (j = 0; j < node->numConns; ++j) {
					if (node->conns[j] >= startNode && node->conns[j] < endNode) {
						--conns;

						MPI_Send(&node->conns[j], 1, MPI_INT, proc, 0, MPI_COMM_WORLD);					
						MPI_Send(&node->connDists[j], 1, MPI_DOUBLE, proc, 0, MPI_COMM_WORLD);					
					}
				}
				
				assert (0 == conns);
			}
		} else {
			MPI_Recv(&node->numConns, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

			node->conns = new(int, node->numConns);
			node->connDists = new(double, node->numConns);

			for (j = 0; j < node->numConns; ++j) {
				MPI_Recv(&node->conns[j], 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				MPI_Recv(&node->connDists[j], 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			}
		}
	}
}


/**
	Helper func for genRandGraph. Returns true if node 'i' is already connected to node 'j'
*/
bool alreadyConnected(Graph graph, int i, int j) {
	int x;
	
	for (x = 0; x < graph.nodes[i].numConns; ++x) {
		if (graph.nodes[i].conns[x] == j) return true;
	}
	
	return false;
}



void printPath(Graph graph, int cur, int source) {
	int prev = graph.prev[cur];
	
	if (0 != cur) {
		if (-1 != prev) {
			printPath(graph, prev, source);
			printf(" -> %d", cur);
		}
	} else {
		printf("0");
	}
}


void printGraph(Graph graph) {
	int i;
	
	for (i = 0; i < graph.numNodes; ++i) {
		printf("node %d  dist : %lf   ", i, dist_max == graph.dists[i] ? -1 : graph.dists[i]);
		printPath(graph, i, 0);
		printf("\n");
	}
}


void printGraphConns(Graph graph) {
	int i, j;
	Node* node;

	for (i = 0; i < graph.numNodes; ++i) {
		node = &graph.nodes[i];

		printf("Node %d conns:", i);

		for (j = 0; j < node->numConns; ++j) {
			printf(" %d", node->conns[j]);
		}

		printf("\n");
	}
}

int printGraphConnsModToFile(Graph graph, char* file) {
	int i, j;
	Node* node;
	FILE* fp;

	fp = fopen(file, "w");
	if (!fp) {
		printf("Nie mozna otworzyc pliku wynikowego.\n");
		return 1;
	}
	fprintf(fp, "%d\n", graph.numNodes);

	for (i = 0; i < graph.numNodes; ++i) {
		node = &graph.nodes[i];

		fprintf(fp, "%d", node->numConns);

		for (j = 0; j < node->numConns; ++j) {
			fprintf(fp, " %d", node->conns[j]);
		}
		fprintf(fp, "\n");
	}
	fclose(fp);
	return 0;
}



void reduceGraph(Graph graph, int startNode, int endNode) {
	int i, j, k, conI;
	Node* node;

	for (i = 0; i < graph.numNodes; ++i) {
		node = &graph.nodes[i];
		k = 0;
	
		for (j = 0; j < node->numConns; ++j) {
			conI = node->conns[j];
	
			if (conI >= startNode && conI < endNode) {
				node->conns[k] = conI;
				node->connDists[k] = node->connDists[j];
				++k;
			}
		}
		
		node->numConns = k;
	}
}


void graphNodeConnect(Node* node, int to, double dist) {
	// make some more space
	node->conns = cast(int*)realloc(node->conns, node->numConns * sizeof(int) + sizeof(int));
	node->connDists = cast(double*)realloc(node->connDists, node->numConns * sizeof(double) + sizeof(double));
	
	// and add the connection
	node->conns[node->numConns] = to;
	node->connDists[node->numConns] = dist;
	++node->numConns;
}


void graphToTreeFromPrevList(Graph graph) {
	int i, prev;
	Node* node;
	
	
	// remove all connections so far
	for (i = 0; i < graph.numNodes; ++i) {
		node = &graph.nodes[i];
		node->numConns = 0;
		free(node->conns);
		node->conns = null;
		free(node->connDists);
		node->connDists = null;
	}
	
	
	for (i = 0; i < graph.numNodes; ++i) {
		prev = graph.prev[i];
		
		// the root vertex or some funky error... anyway, we don't want cycles
		if (i == prev || -1 == prev) continue;

		graphNodeConnect(&graph.nodes[prev], i, 1);
		graphNodeConnect(&graph.nodes[i], prev, 1);
	}
}

